/*
inputs:
6 19000 10000 18000 10000 32000 10000 21000 10000 1234 5678 14000 10000
8 10000 0 0  10000 3000   7000 7000   3000 20000  21000 3000   4000 14000  15000 6000   7000
*/

#include <iostream> 
#include <boost/random.hpp>
#include <boost/foreach.hpp>
#include <boost/lexical_cast.hpp>
#include <set>
#include <map>
#include <vector>

using namespace std;
using namespace boost;
using namespace boost::random;

class Vertex {
private:
	int x, y;
public:
	Vertex( int x, int y ) {
		this->x = x;
		this->y = y;
	}
	
	double slopeTo( Vertex v ) const {
		return ( ( (float)v.y - this->y ) / ( v.x - this->x ) );
	}
	
	int getX() const {
		return this->x;
	}
	
	int getY() const {
		return this->y;
	}
};

ostream & operator<<( ostream & out, const Vertex & v) {
	out << "(" + lexical_cast<string>( v.getX() ) + ", " + lexical_cast<string>( v.getY() ) + ")";
	return out;
}

class VertexCompare: public binary_function< Vertex, Vertex, bool > {
public:
	bool operator()( Vertex v1, Vertex v2 ) {
		return ( v1.getX() < v2.getX() );
	}
};

int main( int argc, char * argv[] ) {
	vector<Vertex> v_v;
	typedef multimap< 	double, pair< int, int > > multimap_of_slope; 
	multimap_of_slope *m_s;
	/*
	mt19937 generator( time( NULL ) );
	uniform_int_distribution< int > distribution( 1, 100 );
	Vertex *v;
	for( int i = 0; i < 10; i++ ) {
		v = new Vertex( distribution( generator ), distribution( generator ) );
		v_v.push_back( *v );
		delete v;
	}
	*/
	int a,b,num=0;
	Vertex *v;
	cout << "Enter number of inputs:";
	cin >> num;
	while( num ) {
		cin >> a >> b;
		v = new Vertex( a, b );
		v_v.push_back( *v );
		delete v;
		
		num--;
	}


	cout << "v_v: ";
	BOOST_FOREACH( Vertex v, v_v ) {
		cout << "\n" << v ;
	}
	cout << endl;
	
	double slope;
	int i, j;
	int max_num_points=0;
	int slope_count;
	set < vector <int> *> max_line;
	vector< int > * v_temp;

	for(  i = 0; i != v_v.size(); i++ ) {
		m_s = new multimap_of_slope();
		for( j = i+1; j != v_v.size(); j++ ) {
			//cout << endl << i << " -> " <<  j;
			//cout.flush();
			slope = ( v_v[ i ] ).slopeTo( v_v[ j ] );
			//cout << " = " << slope << endl;
			m_s->insert( make_pair(slope, make_pair< int, int > ( i, j ) ) );
		}
		//cout << "m_s->size() = " << m_s->size() << endl;
		for
		( 
			multimap_of_slope::iterator iter=m_s->begin(); 
			iter != m_s->end(); 
			iter = m_s->upper_bound( (*iter).first ) 
		) 
		{
			slope_count = m_s->count( iter->first );
			if( slope_count > 2 && slope_count >= max_num_points ) 
			{
				//cout << "slope(" << iter->first << ") has count >2" << endl;
				if( max_num_points < slope_count ) 
				{
					max_line.erase( max_line.begin(), max_line.end() );
					max_num_points = slope_count;
				}
				
				v_temp = new vector< int >();
				
				max_line.insert( v_temp );
				v_temp->push_back( iter->second.first );
				for
				( 
					multimap_of_slope::iterator iter_same_key = m_s->equal_range( (*iter).first ).first; 
					iter_same_key != m_s->equal_range( (*iter).first ).second; 
					++iter_same_key 
				) 
				{
					v_temp->push_back( iter_same_key->second.second );
				}
				cout << endl;
			}
		}
		delete m_s;
	}
	
	BOOST_FOREACH( vector<int> *i, max_line ) {
		BOOST_FOREACH( int j, *i ) {
			cout << "\t" << v_v[ j ];
		}
		cout << endl;
	}
	cout << endl;
}